/**
 * DelSameNode.java created by zhangzhidong 
 * at 下午3:19:08 2016年10月18日
 */
package algorithm;

/**
 * @author zhangzhidong<br>
 * comment generated at 2016年10月18日下午3:19:08<br>
 * 
 */
class ListNode{
	int val;
	ListNode next;
	public ListNode(int val) {
		this.val = val;
	}
	public String toString(){
		return ""+val;
	}
}
public class DelSameNode {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null) return pHead;
		return delete(pHead);
    }
    public ListNode delete(ListNode head){
     	ListNode cur = head;
        ListNode pre = null;
        while(cur!=null){
            ListNode next = cur.next;
            //found same
            if(next != null && next.val == cur.val){
                while(next!=null && next.val == cur.val){
					next = next.next;
				}
              	if(next == null){
					if(pre == null){
                     	head = null;
                        return head;	
                    }else{
                        pre.next = null;
                        return head;
                    }
                }else{
                     if(pre == null){
						head = next;
                        cur = head;
                         pre = null;
					}else{
						pre.next = next;

                        cur = pre.next;
           			 }
                }
            }else{
            	pre = cur;
            	cur = cur.next;
            }
	
        }
		return head;
    }
	public static void main(String[] args) {
		DelSameNode dsn = new DelSameNode();
		int vals[] = new int []{1,1,2,3,3,4,5,5};
		ListNode head = null;
		ListNode pre = null;
		ListNode cur = null;
		for(int i=0;i<vals.length;i++){
			if(i==0){
				head = new ListNode(vals[i]);
				cur = head;
			}else{
				pre = cur;
				cur.next = new ListNode(vals[i]);
				cur = cur.next;
			}
		}
		ListNode t = head;
		while(t!=null){
			System.out.println(t.val);
			t = t.next;
		}
		dsn.deleteDuplication(head);
	}

}
